/*
 * =====================================================================================
 *
 *       Filename:  CursorList.hpp
 *
 *    Description:  implement list by array
 *
 *        Version:  1.0
 *        Created:  2017年05月06日 14时24分51秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Crane ()
 *   Organization:
 *
 * =====================================================================================
 */



#ifndef  CursorList_H_
#define  CursorList_H_

template <class T>
class ListSlot;

const int  kNoFree = -1;
const int  kNullList  = -1;

const int kLIST_SUC     =  0;
const int kLIST_ERROR   = -1;
const int kLIST_NOSPACE = kNoFree;

template <class T>
class CursorList
{
    typedef  ListSlot<T>   Slot;
    typedef  ListSlot<T>  *Slots;

public:
    CursorList(int size = 10) : m_size(size) {
        ListInit();
    }

    ~CursorList() {
        delete [] m_slots;
    }

    // 在position之后, 插入数据ele. position 一般是由Find() 返回的position
    int Insert(T ele, int position)
    {
        int freeNext = allocateSlot();
        if (freeNext < 0)
            return freeNext;

        return insert(ele, freeNext, position);
    }

    int Delete(T ele) {
        return kLIST_SUC;
    }

    // 返回ele所在position
    int Find(T ele) {
        return kLIST_SUC;
    }

    // 返回ele所在的position前一个逻辑pre, 即链接position的位置.
    int FindPrevious(T ele) {
        return kLIST_SUC;
    }

private:    // private operation

    // called by constructor
    void ListInit() {
        m_slots = new Slot[m_size];

        m_freeHeader =  0;
        m_listHeader = kNullList;

        for (int i = 0; i < m_size; i++)
            m_slots[i].SetNext( i + 1);

        m_slots[m_size - 1].SetNext(kNoFree);
    }

    int allocateSlot() {
        if ( ! hasSlot())
            return kLIST_NOSPACE;

        int freeNext = getFreeHeader();
        setFreeHeader( m_slots[freeNext].GetNext() );

        return freeNext;
    }

    int getFreeHeader() {
        return m_freeHeader;
    }

    void setFreeHeader(int newHeader) {
        m_freeHeader = newHeader;
    }

    int hasSlot() {
        return m_freeHeader != kNoFree;
    }

    int insert(T ele, int freeNext, int position) {

        Slot &insertSlot = m_slots[freeNext];
        insertSlot.SetValue(ele);

        Slot &preSlot = m_slots[position];

        insertSlot.SetNext( preSlot.GetNext() );
        preSlot.SetNext( freeNext );

        return kLIST_SUC;
    }

private:
    int   m_freeHeader;
    int   m_listHeader;
    int   m_size;

    Slots m_slots;       // 存储数据用的.
};

template <class T>
class ListSlot
{
public:
    T    m_ele;
    int  m_nextIndex;

    int GetNext() {
        return m_nextIndex;
    }

    void SetNext(int next) {
        m_nextIndex = next;
    }

    T GetValue() {
        return m_ele;
    }

    void SetValue(T ele) {
        m_ele = ele;
    }
};

#endif   /* ----- #ifndef CursorList_H_  ----- */
